#include"list.h"

static void swap_node(struct list *lnode, struct list *rnode) {
	void* tmp = lnode->value;
	lnode->value = rnode->value;
	rnode->value = tmp;
}

void list_init(struct list *l) {
	l->value = 0;
	l->prev = l;
	l->next = l;
}
struct list* list_get_tail(struct list *l) {
	return l->prev;
}

struct list* list_get_head(struct list *l) {
	return l->next;
}

void list_add_tail(struct list *l, void *element) {
	struct list *p;
	struct list *node = (struct list *)malloc(sizeof(struct list));
	node->value = element;
	p = l->prev;
	p->next = node;
	node->prev = p;
	node->next = l;
	l->prev = node;
}

void list_add_head(struct list *l, void *element) {
	struct list * p;
	struct list *node = (struct list *)malloc(sizeof(struct list));
	node->value = element;
	p = l->next;
	p->prev = node;
	node->next = p;
	node->prev = l;
	l->next = node;
}


unsigned list_length(struct list *l) {
	if (l->next == l)
		return 0;
	unsigned count = 0;
	struct list *cur;
	list_foreach(cur, l) {
		count++;
	}
	return count;
}

void list_remove(struct list *l, struct list *node) {
	if (node == l)
		return;
	struct list *prev = node->prev;
	struct list *next = node->next;
	prev->next = next;
	next->prev = prev;
	free(node);
	node = 0;
}

void list_clear(struct list *l) {
	struct list *cur, *next;
	cur = l->next;
	while (cur != l) {
		next = cur->next;
		list_remove(l, cur);
		cur = next;
	}
}
static void _list_sort(struct list *begin, struct list *end, int(*cmp)(void *lp, void *rp)) {
	if (begin == end) {
		return;
	}
	void *pivot = begin->value;
	struct list *head, *tail;
	head = begin;
	tail = end;
	while (1) {
		while (begin != end && cmp(end->value, pivot) >= 0) {
			end = end->prev;
		}
		while (begin != end && cmp(begin->value, pivot) < 0) {
			begin = begin->next;
		}
		if (begin != end) {
			swap_node(begin, end);
		}
		else {
			break;
		}
	}
	swap_node(begin, head);
	if (head != tail) {
		_list_sort(head, begin, cmp);
	}
	if (head != tail) {
		_list_sort(end->next, tail, cmp);
	}
}
void list_sort(struct list *l, int(*cmp)(void *lp, void *rp)) {
	if (l->next == l->prev)
		return;
	struct list *head, *tail;
	head = l->next;
	tail = l->prev;
	_list_sort(head, tail, cmp);
}

void list_reverse(struct list *l) {
	if (l->next == l) {
		return l;
	}
	struct list *cur = l->next;
	while (cur != l) {
		struct list *tmp = cur->next;
		cur->next = cur->prev;
		cur->prev = tmp;
		cur = tmp;
	}
	struct list *tmp = l->next;
	l->next = l->prev;
	l->prev = tmp;
}